/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package core;

//import java.util.ArrayList;
//import java.util.Vector;

/**
 *
 * @author hapsari
 */
public class Astar {
    private int notStarted = 0;// path-related constants
    private boolean walkable = true, unwalkable = false;// walkability array constants
    private int onClosedList;
    private boolean found = true, nonexistent = false;	

//    public ArrayList<Integer[]> lala = new ArrayList<Integer[]>();
    public static boolean walkability[][] = new boolean[Map.getMapWidth()][Map.getMapHeight()];
    private int openList[]= new int[Map.getMapWidth()*Map.getMapHeight()+2]; //1 dimensional array holding ID# of open list items
    private int whichList[][]= new int[Map.getMapWidth()*Map.getMapHeight()+2][Map.getMapWidth()*Map.getMapHeight()+2]; 
        //2 dimensional array used to record whether a cell is on the open list or on the closed list.
    private int openX[]= new int[Map.getMapWidth()*Map.getMapHeight()+2]; //1d array stores the x location of an item on the open list
    private int openY[]= new int[Map.getMapWidth()*Map.getMapHeight()+2]; //1d array stores the y location of an item on the open list
    private int parentX[][]= new int[Map.getMapWidth()][Map.getMapHeight()]; //2d array to store parent of each cell (x)
    private int parentY[][]= new int[Map.getMapWidth()][Map.getMapHeight()]; //2d array to store parent of each cell (y)
    private int Fcost[]= new int[Map.getMapWidth()*Map.getMapHeight()+2]; //1d array to store F cost of a cell on the open list
    private int Gcost[][]= new int[Map.getMapWidth()][Map.getMapHeight()]; //2d array to store G cost for each cell.
    private int Hcost[]= new int[Map.getMapWidth()*Map.getMapHeight()+2]; //1d array to store H cost of a cell on the open list
	
    public int pathLength;     //stores length of the found path for critter
    
    public int pathBankX[]= new int[Map.getMapWidth()*Map.getMapHeight()+2];
    public int pathBankY[]= new int[Map.getMapWidth()*Map.getMapHeight()+2];
    
	
    Astar() {
    }

    public boolean findpath (int startX, int startY, int targetX, int targetY)
	{
        int onOpenList=0, parentXval=0, parentYval=0,
        a=0, b=0, m=0, u=0, v=0, temp=0, numberOfOpenListItems=0,
        addedGCost=0, tempGcost = 0, x=0, y=0,
        tempx, pathX, pathY, 
        newOpenListItemID=0;
        boolean path=false;

        //If starting location and target are in the same location
        if (startX == targetX && startY == targetY)
            return found;

        //Reset variables
        walkability[targetX][targetY] = true;
        onClosedList = 2; 
        onOpenList = 1;
        pathLength = notStarted;// = 0
        Gcost[startX][startY] = 0;
        for (x = 0; x < Map.getMapWidth(); x++)
        {
            for (y = 0; y < Map.getMapHeight();y++)
                whichList [x][y] = 0;
        }

        //Add the starting location to the open list of squares to be checked.
        numberOfOpenListItems = 1;
        openList[1] = 1;//assign it as the top (and currently only) item in the open list, which is maintained as a binary heap
        openX[1] = startX ; openY[1] = startY;

        //Do the following until a path is found or deemed nonexistent.
        do
        {
            //If the open list is not empty, take the first cell off of the list.
            //This is the lowest F cost cell on the open list.
            if (numberOfOpenListItems != 0)
            {
                //Pop the first item off the open list.
                parentXval = openX[openList[1]];
                parentYval = openY[openList[1]]; //record cell coordinates of the item
                whichList[parentXval][parentYval] = onClosedList;//add the item to the closed list

                //Open List = Binary Heap: Delete this item from the open list, which is maintained as a binary heap.
                numberOfOpenListItems = numberOfOpenListItems - 1;//reduce number of open list items by 1	

                //Delete the top item in binary heap and reorder the heap, with the lowest F cost item rising to the top.
                openList[1] = openList[numberOfOpenListItems+1];//move the last item in the heap up to slot #1
                v = 1;

                //Repeat the following until the new item in slot #1 sinks to its proper spot in the heap.
                do
                {
                    u = v;		
                    if (2*u+1 <= numberOfOpenListItems) //if both children exist
                    {
                        //Check if the F cost of the parent is greater than each child.
                        //Select the lowest of the two children.
                        if (Fcost[openList[u]] >= Fcost[openList[2*u]]) 
                            v = 2*u;
                        if (Fcost[openList[v]] >= Fcost[openList[2*u+1]]) 
                            v = 2*u+1;		
                    }
                    else
                    {
                        if (2*u <= numberOfOpenListItems) //if only child #1 exists
                        {
                            //Check if the F cost of the parent is greater than child #1	
                            if (Fcost[openList[u]] >= Fcost[openList[2*u]]) 
                                v = 2*u;
                        }
                    }

                    if (u != v) //if parent's F is > one of its children, swap them
                    {
                        temp = openList[u];
                        openList[u] = openList[v];
                        openList[v] = temp;			
                    }
                    else
                        break; //otherwise, exit loop
                }
                while (true);//reorder the binary heap

                //Check the adjacent squares. Add these adjacent child squares to the open list
                //for later consideration if appropriate
                for (b = parentYval-1; b <= parentYval+1; b++)
                {
                    for (a = parentXval-1; a <= parentXval+1; a++)
                    {
                        //Not allowed to walk diagonal
                        if (Math.abs(b-parentYval)==1 && Math.abs(a-parentXval)==1)
                            continue;
                        //If not off the map (do this first to avoid array out-of-bounds errors)
                        if (a != -1 && b != -1 && a != Map.getMapWidth() && b != Map.getMapHeight())
                        {
                            // If not already on the closed list (items on the closed list have
                            // already been considered and can now be ignored).			
                            if (whichList[a][b] != onClosedList) 
                            { 
                                // If not a wall/obstacle square.
                                if (walkability [a][b] != unwalkable) 
                                {
                                    // If not already on the open list, add it to the open list.			
                                    if (whichList[a][b] != onOpenList) 
                                    {	
                                        //Create a new open list item in the binary heap.
                                        newOpenListItemID = newOpenListItemID + 1; //each new item has a unique ID #
                                        m = numberOfOpenListItems+1;
                                        openList[m] = newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap
                                        openX[newOpenListItemID] = a;
                                        openY[newOpenListItemID] = b;//record the x and y coordinates of the new item

                                        //Figure out its G cost
                                        if (Math.abs(a-parentXval) == 1 && Math.abs(b-parentYval) == 1)
                                            addedGCost = 14;//cost of going to diagonal squares	
                                        else	
                                            addedGCost = 10;//cost of going to non-diagonal squares				
                                        Gcost[a][b] = Gcost[parentXval][parentYval] + addedGCost;
                                                                                
                                        //Figure out its H and F costs and parent
                                        Hcost[openList[m]] = 10*(Math.abs(a - targetX) + Math.abs(b - targetY));
                                        Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]];
                                        parentX[a][b] = parentXval ; parentY[a][b] = parentYval;	

                                        //Move the new open list item to the proper place in the binary heap.
                                        //Starting at the bottom, successively compare to parent items,
                                        //swapping as needed until the item finds its place in the heap
                                        //or bubbles all the way to the top (if it has the lowest F cost).
                                        while (m != 1) //While item hasn't bubbled to the top (m=1)	
                                        {
                                            //Check if child's F cost is < parent's F cost. If so, swap them.	
                                            if (Fcost[openList[m]] <= Fcost[openList[m/2]])
                                            {
                                                temp = openList[m/2];
                                                openList[m/2] = openList[m];
                                                openList[m] = temp;
                                                m = m/2;
                                            }
                                            else
                                                break;
                                        }
                                        numberOfOpenListItems = numberOfOpenListItems+1;//add one to the number of items in the heap

                                        //Change whichList to show that the new item is on the open list.
                                        whichList[a][b] = onOpenList;
                                    }
                                    //If adjacent cell is already on the open list, check to see if this 
                                    //path to that cell from the starting location is a better one. 
                                    //If so, change the parent of the cell and its G and F costs.	
                                    else //If whichList(a,b) = onOpenList
                                    {
                                        //Figure out the G cost of this possible new path
                                        if (Math.abs(a-parentXval) == 1 && Math.abs(b-parentYval) == 1)
                                            addedGCost = 14;//cost of going to diagonal tiles	
                                        else	
                                            addedGCost = 10;//cost of going to non-diagonal tiles				
                                        tempGcost = Gcost[parentXval][parentYval] + addedGCost;

                                        //If this path is shorter (G cost is lower) then change
                                        //the parent cell, G cost and F cost. 		
                                        if (tempGcost < Gcost[a][b]) //if G cost is less,
                                        {
                                            parentX[a][b] = parentXval; //change the square's parent
                                            parentY[a][b] = parentYval;
                                            Gcost[a][b] = tempGcost;//change the G cost			
                                            //Because changing the G cost also changes the F cost, if
                                            //the item is on the open list we need to change the item's
                                            //recorded F cost and its position on the open list to make
                                            //sure that we maintain a properly ordered open list.
                                            for (x = 1; x <= numberOfOpenListItems; x++) //look for the item in the heap
                                            {
                                                if (openX[openList[x]] == a && openY[openList[x]] == b) //item found
                                                {
                                                    Fcost[openList[x]] = Gcost[a][b] + Hcost[openList[x]];//change the F cost

                                                    //See if changing the F score bubbles the item up from it's current location in the heap
                                                    m = x;
                                                    while (m != 1) //While item hasn't bubbled to the top (m=1)	
                                                    {
                                                        //Check if child is < parent. If so, swap them.	
                                                        if (Fcost[openList[m]] < Fcost[openList[m/2]])
                                                        {
                                                            temp = openList[m/2];
                                                            openList[m/2] = openList[m];
                                                            openList[m] = temp;
                                                            m = m/2;
                                                        }
                                                        else
                                                            break;
                                                    } 
                                                    break; //exit for x = loop
                                                } //If openX(openList(x)) = a
                                            } //For x = 1 To numberOfOpenListItems
                                        }//If tempGcost < Gcost(a,b)
                                    }//else If whichList(a,b) = onOpenList	
                                }//If not a wall/obstacle square.
                            }//If not already on the closed list 
                        }//If not off the map
                    }//for (a = parentXval-1; a <= parentXval+1; a++){
                }//for (b = parentYval-1; b <= parentYval+1; b++){
            }//if (numberOfOpenListItems != 0)
            //If open list is empty then there is no path.	
            else
            {
                path = nonexistent; 
                break;
            }  

            //If target is added to open list then path has been found.
            if (whichList[targetX][targetY] == onOpenList)
            {
                path = found; 
                break;
            }
        }
        while (true);//Do until path is found or deemed nonexistent

        //Save the path if it exists.
        if (path == found)
        {
            //Working backwards from the target to the starting location by checking
            //each cell's parent, figure out the length of the path.
            pathX = targetX; pathY = targetY;
            do
            {
                //Look up the parent of the current cell.	
                tempx = parentX[pathX][pathY];		
                pathY = parentY[pathX][pathY];
                pathX = tempx;

                //Figure out the path length
                pathLength = pathLength + 1;
            }
            while (pathX != startX || pathY != startY);
        }
        return path;
    }
	
    public void ReadPath(int startX, int startY, int targetX, int targetY)
    {
        pathBankX[pathLength]=targetX;
        pathBankY[pathLength]=targetY;
        for (int i = pathLength-1; i>=0; i--)
        {
            pathBankX[i]=parentX[pathBankX[i+1]][pathBankY[i+1]];
            pathBankY[i]=parentY[pathBankX[i+1]][pathBankY[i+1]];
//            System.out.println("Astar path["+i+"] "+pathBankX[i]+","+pathBankY[i]);
        }
        
//        Integer in = new Integer(20);
//        lala.add(0,in);
//        System.out.println("lala "+lala.get(0)+in.intValue());
    }
}
